package com.example.find.activity;

import android.os.Bundle;
import android.support.annotation.Nullable;
import android.support.v7.app.AppCompatActivity;
import android.util.Log;
import android.view.View;
import android.widget.TextView;

import com.example.find.R;
import com.example.find.R2;

import butterknife.BindView;
import butterknife.ButterKnife;
import butterknife.OnClick;

//排序算法
public class SortingAlgorithmActivity extends AppCompatActivity{


    @BindView(R2.id.tv_start_data)
    TextView tvStartData;
    @BindView(R2.id.tv_end_data)
    TextView tvEndData;

    private int a[] = {3,1,5,7,2,4,9,6};
    private int b[] = {6,4,9,3,6,2,8,7};
    private String startStr = "";
    private String endStr  = "";

    @Override
    protected void onCreate(@Nullable Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_sorta_algorithm_layout);
        ButterKnife.bind(this);
        for (int i = 0; i < b.length; i++) {
            startStr = startStr + b[i] + ",";
        }
        tvStartData.setText("原序："+ startStr.substring(0,startStr.lastIndexOf(",")));
    }


    @OnClick({R2.id.straight_insertion_btn,R2.id.straight_shell_btn})
    public void onClick(View view){
        int id = view.getId();
        if(id  == R.id.straight_insertion_btn){  //插入排序—直接插入排序
//            insertSort(a,8);
            insertSortCopy(b,8);
        }else if(id == R.id.straight_shell_btn){ //希尔排序
            shellSort(b,8);
        }
    }

    /**
     * 插入排序—直接插入排序    低 ---> 高
     * @param a
     * @param n
     */
    public void insertSort(int a[], int n){
        long l = System.currentTimeMillis();
        for(int i= 1; i<n; i++){
            if(a[i] < a[i-1]){               //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
                int j= i-1;
                int x = a[i];        //复制为哨兵，即存储待排序元素
                a[i] = a[i-1];           //先后移一个元素
                while(j >= 0 && x < a[j]){  //查找在有序表的插入位置
                    a[j+1] = a[j];
                    j--;         //元素后移
                }
                a[j+1] = x;      //插入到正确位置
            }
//            print(a,n,i);           //打印每趟排序的结果
        }
        long l1 = System.currentTimeMillis();
        Log.e("is end time:",(l1 - l)+"");
        print("原型插入排序结果: ",a,n);           //打印每趟排序的结果
    }

    /**
     * 打印
     * @param a
     * @param n
     * @param i
     */
    private void print(String name,int a[],int n,int i){
        Log.e("insertSort-","i="+i);
        for(int j = 0; j < a.length; j++){
            Log.e("insertSort-","a[j]="+a[j]);
        }
        Log.e("insertSort-","end");

    }

    /**
     * 打印
     * @param a
     * @param n
     */
    private void print(String name,int a[],int n){
        endStr = "";
        for(int j = 0; j < a.length; j++){
            endStr = endStr + a[j] + ",";
            Log.e("insertSort-","a[j]="+a[j]);
        }
        tvEndData.setText(name+ endStr.substring(0,endStr.lastIndexOf(",")));
        Log.e("insertSort-","end");

    }



    ////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////

    /**
     * 自写直接插入排序  高 ---> 低
     * @param a
     * @param n
     */
    private void insertSortCopy(int a[],int n){

        for (int i = 1; i < n; i++) {

            if(a[i] > a[i-1]){

                int j = i -1;

                int x = a[i];

                a[i] = a[i -1];

                while(j >= 0 && x > a[j]){  //对有序数组部分排序 0 --> j

                    a[j + 1] = a[j];

                    j--;

                }

                a[j + 1] = x;
            }

        }
        print("自写插入排序结果: ",a,n);
    }


    /**
     * 希尔排序
     * @param a
     * @param n
     */
    private void shellSort(int a[],int n){
        int dk = n/2;
        while (dk >= 1){
            shellInsertSort(a,n,dk);
            dk = dk/2;
        }
    }

    /**
     * 希尔插入排序
     * @param a
     * @param n
     * @param dk
     */
    private void shellInsertSort(int a[],int n,int dk){
        for (int i = dk; i < n; i++) {
            if(a[i] < a[i - dk]){

                int j = i - dk;

                int x = a[i];

                a[i] = a[i - dk];

                while(j >= 0 && x < a[j]){

                    a[i - dk] = a[j];

                    j -= dk;
                }
                a[j + dk] = x;
            }
        }

        print("希尔排序结果: ",a,n);
    }

}
